Ramanujan Graphs and the Matrix Completion Problem

Abstract: Graphs consist of vertices, and edges between vertices. A graph is said to be d-regular if every vertex has degree d, that is, exactly d other vertices connected to it. For each graph one can associate an Adjacency matrix A, of size n by n where n is the number of vertices. If the graph is d-regular, then d is always an eigenvalue of A. Such a graph is called a "Ramanujan graph" if the second largest eigenvalue of A is no larger than twice the square root of d-1. In this talk I will explain where this rather strange-looking bound comes from, and show that in fact it is the best one can achieve in any graph as n becomes large. Explicit constructions of Ramanujan graphs are still very few, and I will provide a couple of such procedures. Finally, I will discuss the "matrix completion problem" which has applications in many engineering domains, and show how it can be solved using Ramanujan graphs.

Mathematics

Audience: general audience

Gonit Sora Webinars for Students

Series comments: The Zoom link and talk details are sent to the mailing list 1-2 days before the event. To register please visit the website: gonitsora.com/webinars/